|
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that his allocated share is at least as good as any other share, according to his own subjective valuation. When there are only 2 partners, the problem is easy and has been solved in Biblical times by the divide and choose protocol. When there are 3 or more partners, the problem becomes much more challenging. When there are 4 or more partners, it is not even known whether the problem can be solved in bounded time. Two major variants of the problem have been studied: * Connected pieces, e.g. if the cake is a 1-dimensional interval then each partner must receive a single sub-interval. If there are partners, only cuts are needed. * General pieces, e.g. if the cake is a 1-dimensional interval then each partner can receive a union of disjoint sub-intervals. == Short history == The modern research of the fair cake-cutting problem has started in the 1940s. The first fairness criterion studied was proportional division, and a procedure for ''n'' partners has been found soon. The stronger criterion of envy-freeness was introduced into the cake-cutting problem by George Gamow and Marvin Stern in 1950s. A procedure for 3 partners and general pieces was found in 1960 and a procedure for 3 partners and connected pieces - only in 1980. Envy-free division for 4 or more partners has been an open problem until the 1990s, when three procedures for general pieces and a procedure for connected pieces have been published. All these procedures are ''unbounded'' - they may require a number of steps which is not bounded in advance. The procedure for connected pieces may even require an ''infinite'' number of steps. Two lower bounds on the run-time complexity of envy-freeness have been published in the 2000s. * For general pieces, the lower bound is Ω(''n''2). This is very far below the best known procedures. It is not known whether there exist bounded-time procedures for 4 or more partners. * For connected pieces the lower bound is infinity - there is provably no finite protocol for 3 or more partners. However, this hardness result assumes that the entire cake must be divided. If this requirement is replaced by the weaker requirement that every partner receives a proportional value (at least 1/''n'' of the total cake value according to his own valuation), then a bounded procedure for 3 partners is known, but it is still an open problem whether there exist bounded-time procedures for 4 or more partners. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Envy-free cake-cutting」の詳細全文を読む スポンサード リンク
|